1. Field of the Invention
The present invention relates to an image processing system, and more particularly, to a system for matching a stereo image of a video image sequence in a real-time mode.
2. Description of the Related Art
Stereo matching is the core process of a stereo vision in which 3-dimensional spatial information is re-created using a pair of 2-dimensional images. In an article [Uemsh R. Dhond and J. K. Aggarwal. Structure from stereo—a review. IEEE Transactions on Systems, Man, and Cybernetics, 19(6):553-572, November/December 1989], basic issues related to stereo vision and some important research fields can be found. Typically, a pair of cameras having the same optical characteristics are aligned with focal planes on the same plane. This permits the horizontal scan lines to be the same in each image. If a pixel in each image corresponding to the same point in a 3-dimensional space can be found, the distance to the 3-dimensional (3-D) point from the cameras can be found using a simple geometrical characteristics. Some pixels in each image may not have matching pixels in the other image, which is known as an occlusion. In the processing, the most difficult part is to find the matching pixels, that is, a stereo matching.
3-D reconstruction is very important in such fields as mapping, geology, testing, inspection, navigation, virtual reality, medicine, etc. Many of these fields require the information in real-time because the fields must respond immediately to information available. This is especially true in robotics and autonomous vehicles.
In an article [Stuart Geman and Donald Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-6(6):721-741, November 1984], a stereo matching method using Markov random fields and stochastic optimization methods, based on simulated annealing presented by S. Kirkpatrick et al., “Optimization by Simulated Annealing”, Science, May 1983, pg. 671-680, is described. This has been further developed by others, for example, Geiger and Girosi using mean field theory. However, this class of methods is iterative in nature resulting in very long computational times that are not suitable for real time stereo matching.
In an article [H. H. Baker and T. O. Binford. Depth from edge and intensity based stereo. In Proceedings of the International Joint Conference on Artificial Intelligence, page 631-636, Vancouver, Canada, 1981] and an article [Y. Ohta and T. Kanade. Stereo by intra- and inter-scan line search. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-7(2):139-154, March 1985], stereo matching methods based on dynamic programming (DP) and heuristic post-processing are described. In an article [Ingemar J. Cox, Sunita L. Hingorani, Satish B. Rao, and Bruce M. Maggs. A maximum likelihood stereo algorithm. Computer Vision and Image Understanding, 63(3):542-567, May 1996] and an article [Stan Birchfield and Carlo Tomasi. Depth discontinuities by pixel-to-pixel stereo. In Proceeding of the IEEE International Conference on Computer Vision, pages 1073-1080m, Bombay, India, 1998], single-level DP in discrete pixel oriented methods are described. In an article [Peter N. Belhumeur. A Bayesian approach to binocular stereopsis. International Journal of Computer Vision, 19(3):237-260, 1996], a more complex DP method with sub-pixel resolution is described. Though this class of methods is much faster than the Markov random field based ones, they do not scale well for parallel processing and are thus still unsuitable for real-time stereo matching.